package com.github.yangyishe;

import java.util.ArrayList;
import java.util.List;

/**
 * 637. 二叉树的层平均值
 * https://leetcode.cn/problems/average-of-levels-in-binary-tree/?envType=study-plan-v2&envId=top-interview-150
 *
 *
 * 给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[3.00000,14.50000,11.00000]
 * 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
 * 因此返回 [3, 14.5, 11] 。
 * 示例 2:
 *
 *
 *
 * 输入：root = [3,9,20,15,7]
 * 输出：[3.00000,14.50000,11.00000]
 *
 *
 * 提示：
 *
 * 树中节点数量在 [1, 104] 范围内
 * -231 <= Node.val <= 231 - 1
 *
 *
 */
public class Problem637 {
    public static void main(String[] args) {
        Integer[] param=new Integer[]{3,9,20,null,null,15,7};
        TreeNode instanceNew = TreeNode.getInstanceNew(param);

        Problem637 problem637 = new Problem637();
        List<Double> doubleList = problem637.averageOfLevels(instanceNew);
        System.out.println(doubleList);
    }

    /**
     * 思路:
     * 以任意一种方式遍历, 遍历函数为记录节点值和与层级节点大小
     * 之后根据遍历结果, 求出平均值即可
     * @param root
     * @return
     */
    public List<Double> averageOfLevels(TreeNode root) {
        preOrder(root,0);

        List<Double> resultList=new ArrayList<>(tmpList.size());
        for (Long[] ints : tmpList) {
            resultList.add(((double) ints[0]) / ints[1]);
        }

        return resultList;
    }

    private List<Long[]> tmpList=new ArrayList<>();
    private void preOrder(TreeNode treeNode,int level){
        if(treeNode==null){
            return;
        }
        if(level==tmpList.size()){
            tmpList.add(new Long[]{(long) treeNode.val,1L});
        }else{
            Long[] integers = tmpList.get(level);
            integers[0]=integers[0]+treeNode.val;
            integers[1]=integers[1]+1;
        }
        preOrder(treeNode.left,level+1);
        preOrder(treeNode.right,level+1);
    }
}
